package A1动态规划;

public class LC_494目标和 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int num:nums)
            sum+=num;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if((sum+target)%2!=0)
            return 0;
        //如果target的绝对值大于sum，那么是没有方案的
        if(Math.abs(target)>sum)
            return 0;
        int bagsize=(sum+target)/2;
        int[] dp=new int[bagsize+1];
        dp[0]=1;
        for(int num:nums)
            for(int j=bagsize;j>=num;j--)
                dp[j]+=dp[j-num];
        return dp[bagsize];
    }
}
